子2023

题目 子2023

思路分析

暴力枚举

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
string s="";
long long cnt=0;
int main()
{
    for(int i=1;i<=2023;i++){
        s+=to_string(i);
    }
//    cout<<s<<'\n';
    for(int i=0;i<s.size()-3;i++){
        if(s[i]!='2')continue;
        for(int j=i+1;j<s.size()-2;j++){
            if(s[j]!='0')continue;
            for(int k=j+1;k<s.size()-1;k++){
                if(s[k]!='2')continue;
                for(int l=k+1;l<s.size();l++){
                    if(s[l]!='3')continue;
                    if(s[i]=='2'&&s[j]=='0'&&s[k]=='2'&&s[l]=='3')cnt++;
                }
            }
        }
    }
    cout<<cnt;
    return 0;
}

优化枚举

把原始序列中的2023四个数字复制到另一个数组

即剔除非2023数字，然后进行四层for循环

#include <bits/stdc++.h>
using namespace std;
int a[5000005];
int n=5000001;
int v[8100];
int k=0;
void f(int v) {
  while (v) {
      a[--n]=v%10;
      v=v/10;
  }
}
 int main() {
  for (int i=2023;i>=1;i--) {
      f(i);
  }
  for(int i=n;i<=5000000;i++)if(a[i]==2||a[i]==0||a[i]==3)v[++k]=a[i];
  long long s[5];
  s[1]=0;s[2]=0;s[3]=0;s[4]=0;
  for(int i=1;i<=k;i++)
      if(v[i]==2){s[1]++;s[3]+=s[2];}
  else if(v[i]==0)s[2]+=s[1];
  else if(v[i]==3)s[4]+=s[3];
  cout<<s[4];
    return 0;
}

或者dp

从前i个字符串中选，长度为j的子序列中等于2023的子序列个数

#include <iostream>
using namespace std;
long long f[7000][5];
int main()
{
    string s;
    string a="s2023";
    s+="x";
    for(int i=1;i<=2023;i++) s+=to_string(i);
    f[0][0]=1;
    int n=s.size()-1;
    for(int i=1;i<=n;i++)
        for(int j=0;j<=4;j++)
        {
            f[i][j]=f[i-1][j];
            if(a[j]==s[i])
            	f[i][j]+=f[i-1][j-1];
        }
    cout<<f[n][4];
    return 0;
}

还是不行

代码实现

同类题型

视频讲解

⬅️ 第十四届蓝桥杯大赛软件赛决赛C/C++ 大学 B 组 🏠 00-冲刺国赛 ➡️ 双子数